// QtCore
#include <QtCore/QVector>
// Локальные
#include "math/math.h"
#include "geometry/2d/geometry.h"
#include "fem/frontaltriangulation.h"

using geometry::_2d::Point;

namespace fem
{
    //================================================================================================================================
    //================================================================================================================================
    FrontalTriangulation::FrontalTriangulation(const QStringList &f_ids) : m_BorderSegmentsBCInfo(f_ids.size())
    {
        for(int i = 0; i < f_ids.size(); ++i)
        {
            Q_ASSERT_X(!m_FunctionsIDTable.contains(f_ids[i]), "FrontalTriangulation::FrontalTriangulation", "function id isn't unique");
            m_FunctionsIDTable[f_ids[i]] = i;
        }
    }

    //================================================================================================================================
    //================================================================================================================================
    void FrontalTriangulation::getDirichletBoundaryInfo(const QString &f_id, QList<int> &points, QList<int> &conditions) const
    {
        Q_ASSERT_X(m_FunctionsIDTable.contains(f_id), "FrontalTriangulation::getDirichletBoundaryInfo", "function id is unknown");

        points.clear();
        conditions.clear();

        for(int i = 0, index = m_FunctionsIDTable[f_id]; i < m_BorderSegmentsBCInfo[index].size(); i++)
        {
            if(m_BorderSegmentsBCInfo[index][i].BCType == 1)
            {
                int segment_id = m_BorderSegmentsBCInfo[index][i].Segment;

                if(!points.contains(m_BorderSegments[segment_id].firstPoint()))
                {
                    points.append(m_BorderSegments[segment_id].firstPoint());
                    conditions.append(m_BorderSegmentsBCInfo[index][i].BCFormula);
                }

                for(int j = 1; j < m_BorderSegments[segment_id].numOfPoints() - 1; j++)
                {
                    points.append(m_BorderSegments[segment_id].point(j));
                    conditions.append(m_BorderSegmentsBCInfo[index][i].BCFormula);
                }

                if(!points.contains(m_BorderSegments[segment_id].lastPoint()))
                {
                    points.append(m_BorderSegments[segment_id].lastPoint());
                    conditions.append(m_BorderSegmentsBCInfo[index][i].BCFormula);
                }
            }
        }
    }

    //================================================================================================================================
    //================================================================================================================================
    int FrontalTriangulation::addBorderSegment(int begin, int end, int num_of_knots)
    {
        QList<int> point_indices;
        point_indices.append(begin);
        for(int i = 0; i < num_of_knots; i++)
        {
            double x = m_Points[begin].x() + (m_Points[end].x() - m_Points[begin].x())*(i + 1)/(num_of_knots + 1);
            double y = m_Points[begin].y() + (m_Points[end].y() - m_Points[begin].y())*(i + 1)/(num_of_knots + 1);
            m_Points.append(Point(x,y));
            point_indices.append(m_Points.size() - 1);
        }
        point_indices.append(end);

        m_BorderSegments.append(BorderSegment(point_indices));
        return m_BorderSegments.size() - 1;
    }

    //================================================================================================================================
    //================================================================================================================================
    int FrontalTriangulation::addBorderSegment(int begin, int end, int num_of_knots, double spacing_factor)
    {
        if(qAbs(spacing_factor - 1) < DBL_EPSILON)
            return addBorderSegment(begin, end, num_of_knots);

        double w = abs(m_Points[begin].x() - m_Points[end].x())*(1 - spacing_factor)/(1 - pow(spacing_factor, num_of_knots + 1));
        double h = abs(m_Points[begin].y() - m_Points[end].y())*(1 - spacing_factor)/(1 - pow(spacing_factor, num_of_knots + 1));

        QList<int> point_indices;
        point_indices.append(begin);
        for(int i = 0; i < num_of_knots; ++i, w*=spacing_factor, h*=spacing_factor)
        {
            double x = m_Points[point_indices.last()].x() + w;
            double y = m_Points[point_indices.last()].y() + h;
            m_Points.append(Point(x,y));
            point_indices.append(m_Points.size() - 1);
        }
        point_indices.append(end);

        m_BorderSegments.append(BorderSegment(point_indices, spacing_factor));
        return m_BorderSegments.size() - 1;
    }

    //================================================================================================================================
    //================================================================================================================================
    void FrontalTriangulation::addBorderSegmentBCInfo(const QString &f_id, int segment, int bc_type, int bc_formula)
    {
        Q_ASSERT_X(m_FunctionsIDTable.contains(f_id), "FrontalTriangulation::addBorderSegmentExtraInfo", "function id is unknown");
        Q_ASSERT_X(bc_type >= 1 && bc_type <= 4, "FrontalTriangulation::addBorderSegmentExtraInfo", "unknown bc type");
        Q_ASSERT_X(bc_type != 0 || bc_formula != -1, "FrontalTriangulation::addBorderSegmentExtraInfo", "default bc_formula value for bc_type 1-3");

        BorderSegmentBCInfo bc_info = {segment, bc_type, bc_formula};
        m_BorderSegmentsBCInfo[m_FunctionsIDTable[f_id]].append(bc_info);
    }

    //================================================================================================================================
    //================================================================================================================================
    TriangleNet FrontalTriangulation::triangulate()
    {
        //****************************************************************************************************************************
        //Триангуляция четырехугольных подобластей
        //****************************************************************************************************************************
        for(int i = 0; i < m_QuadrangleSubdomains.size(); i++)
        {
            prepareQuadrangleSubdomain(i);
            //Сегменты a, b, c и d ограничивающие подобласть.
            BorderSegment &a = m_BorderSegments[m_QuadrangleSubdomains[i].borderSegment(0)];
            BorderSegment &b = m_BorderSegments[m_QuadrangleSubdomains[i].borderSegment(1)];
            BorderSegment &c = m_BorderSegments[m_QuadrangleSubdomains[i].borderSegment(2)];
            BorderSegment &d = m_BorderSegments[m_QuadrangleSubdomains[i].borderSegment(3)];

            //Если есть две противоположные стороны с одинаковым числом узлов, то запускается стандартный алгоритм
            //Функция prepareQuadrangleSubdomain() гарантирует, что если такие стороны есть - то это стороны a и c.
            if(a.numOfPoints() == c.numOfPoints())
                triangulateQuadrangleSubdomain(i);
            //в противном случае четырехугольник разбивается на четырехугольник и треугольник
            else
            {
                int minimal, maximal;
                QList<int> point_indices;
                QList<int> segment_indices;
                int indexes_of_new_segments[3];

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Поскольку от того, какая сторона меньше(a или c) зависит всего лишь одно действие, а именно - определение нового
                //четырехугольника, то введя обозначения minimal и maximal можно повысить читабельность и простоту кода
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                if(a.numOfPoints() < c.numOfPoints())
                {
                    minimal = m_QuadrangleSubdomains[i].borderSegment(0);
                    maximal = m_QuadrangleSubdomains[i].borderSegment(2);
                }
                else
                {
                    minimal = m_QuadrangleSubdomains[i].borderSegment(2);
                    maximal = m_QuadrangleSubdomains[i].borderSegment(0);
                }

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Разбиваем один из сегментов подобласти на два новых сегмента
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                for(int k = 0; k < m_BorderSegments[minimal].numOfPoints(); k++)
                    point_indices.append(m_BorderSegments[maximal].point(k));

                BorderSegment new_segment_1(point_indices);

                point_indices.clear();
                for(int k = m_BorderSegments[minimal].numOfPoints() - 1; k < m_BorderSegments[maximal].numOfPoints(); k++)
                    point_indices.append(m_BorderSegments[maximal].point(k));

                BorderSegment new_segment_2(point_indices);

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Создаем поперечный сегмент, который соединяет сегменты a и c и разбивает подобласть на две
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                point_indices.clear();
                point_indices.append(new_segment_2.point(0));
                for(int j = 1; j < b.numOfPoints() - 1; j++)
                {
                    double x = m_Points[new_segment_2.firstPoint()].x() + (m_Points[m_BorderSegments[minimal].lastPoint()].x() -
                                                                           m_Points[new_segment_2.firstPoint()].x())*j/(b.numOfPoints() - 1);

                    double y = m_Points[new_segment_2.firstPoint()].y() + (m_Points[m_BorderSegments[minimal].lastPoint()].y() -
                                                                           m_Points[new_segment_2.firstPoint()].y())*j/(b.numOfPoints() - 1);

                    m_Points.append(Point(x,y));
                    point_indices.append(m_Points.size() - 1);
                }
                point_indices.append(m_BorderSegments[minimal].lastPoint());
                BorderSegment new_segment_3(point_indices);

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Заносим новые сегменты в список сегментов
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                indexes_of_new_segments[0] = m_BorderSegments.size();
                m_BorderSegments.append(new_segment_1);
                indexes_of_new_segments[1] = m_BorderSegments.size();
                m_BorderSegments.append(new_segment_2);
                indexes_of_new_segments[2] = m_BorderSegments.size();
                m_BorderSegments.append(new_segment_3);

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Создаем квадратную подобласть
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                if(a.numOfPoints() < c.numOfPoints())
                {
                    segment_indices.clear();
                    segment_indices.append(m_QuadrangleSubdomains[i].borderSegment(0));
                    segment_indices.append(indexes_of_new_segments[2]);
                    segment_indices.append(indexes_of_new_segments[0]);
                    segment_indices.append(m_QuadrangleSubdomains[i].borderSegment(3));

                    m_QuadrangleSubdomains.append(Subdomain(segment_indices, m_QuadrangleSubdomains[i].material()));
                }
                else
                {
                    segment_indices.clear();
                    segment_indices.append(indexes_of_new_segments[0]);
                    segment_indices.append(indexes_of_new_segments[2]);
                    segment_indices.append(m_QuadrangleSubdomains[i].borderSegment(2));
                    segment_indices.append(m_QuadrangleSubdomains[i].borderSegment(3));

                    m_QuadrangleSubdomains.append(Subdomain(segment_indices, m_QuadrangleSubdomains[i].material()));
                }

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Создаем треугольную подобласть
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                segment_indices.clear();
                segment_indices.append(m_QuadrangleSubdomains[i].borderSegment(1));
                segment_indices.append(indexes_of_new_segments[1]);
                segment_indices.append(indexes_of_new_segments[2]);

                m_TriangleSubdomains.append(Subdomain(segment_indices, m_QuadrangleSubdomains[i].material()));
            }
        }

        //****************************************************************************************************************************
        //Треугольные подобласти
        //****************************************************************************************************************************
        for(int i = 0; i < m_TriangleSubdomains.size(); i++)
        {
            prepareTriangleSubdomain(i);
            //Сегменты a, b и c ограничивающие подобласть.
            BorderSegment &a = m_BorderSegments[m_TriangleSubdomains[i].borderSegment(0)];
            BorderSegment &b = m_BorderSegments[m_TriangleSubdomains[i].borderSegment(1)];
            BorderSegment &c = m_BorderSegments[m_TriangleSubdomains[i].borderSegment(2)];

            //Если есть две стороны с одинаковым числом узлов, то запускается стандартный алгоритм
            //Функция prepareTriangleSubdomain() гарантирует, что если такие стороны есть - то это стороны a и b.
            if(a.numOfPoints() == b.numOfPoints())
                triangulateTriangleSubdomain(i);
            //Иначе разбиваем треугольник на два
            else
            {
                int minimal, maximal;
                QList<int> point_indices;
                QList<int> segment_indices;
                int indexes_of_new_segments[3];

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Поскольку от того, какая сторона меньше(a или b) алгоритм принципиально не зависит, то введя обозначения minimal и
                //maximal можно повысить читабельность и простоту кода
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                if(a.numOfPoints() < b.numOfPoints())
                {
                    minimal = m_TriangleSubdomains[i].borderSegment(0);
                    maximal = m_TriangleSubdomains[i].borderSegment(1);
                }
                else
                {
                    minimal = m_TriangleSubdomains[i].borderSegment(1);
                    maximal = m_TriangleSubdomains[i].borderSegment(0);
                }

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Разбиваем один из сегментов подобласти на два новых сегмента
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                for(int k = 0; k < m_BorderSegments[minimal].numOfPoints(); k++)
                    point_indices.append(m_BorderSegments[maximal].point(k));

                BorderSegment new_segment_1(point_indices);

                point_indices.clear();
                for(int k = m_BorderSegments[minimal].numOfPoints() - 1; k < m_BorderSegments[maximal].numOfPoints(); k++)
                    point_indices.append(m_BorderSegments[maximal].point(k));

                BorderSegment new_segment_2(point_indices);

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Создаем поперечный сегмент, который соединяет сегменты a и b и разбивает подобласть на две
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                point_indices.clear();
                point_indices.append(new_segment_2.firstPoint());
                for(int j = 1; j < c.numOfPoints() - 1; j++)
                {
                    double x = m_Points[new_segment_2.firstPoint()].x() + (m_Points[m_BorderSegments[minimal].lastPoint()].x() -
                                                                           m_Points[new_segment_2.firstPoint()].x())*j/(c.numOfPoints() - 1);
                    double y = m_Points[new_segment_2.firstPoint()].y() + (m_Points[m_BorderSegments[minimal].lastPoint()].y() -
                                                                           m_Points[new_segment_2.firstPoint()].y())*j/(c.numOfPoints() - 1);

                    m_Points.append(Point(x,y));
                    point_indices.append(m_Points.size() - 1);
                }
                point_indices.append(m_BorderSegments[minimal].lastPoint());

                BorderSegment new_segment_3(point_indices);

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Заносим новые сегменты в список сегментов
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                indexes_of_new_segments[0] = m_BorderSegments.size();
                m_BorderSegments.append(new_segment_1);
                indexes_of_new_segments[1] = m_BorderSegments.size();
                m_BorderSegments.append(new_segment_2);
                indexes_of_new_segments[2] = m_BorderSegments.size();
                m_BorderSegments.append(new_segment_3);

                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                //Создаем две новых треугольных подобласти
                //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
                segment_indices.clear();
                segment_indices.append(m_TriangleSubdomains[i].borderSegment(2));
                segment_indices.append(indexes_of_new_segments[1]);
                segment_indices.append(indexes_of_new_segments[2]);

                m_TriangleSubdomains.append(Subdomain(segment_indices, m_TriangleSubdomains[i].material()));

                segment_indices.clear();
                segment_indices.append(minimal);
                segment_indices.append(indexes_of_new_segments[0]);
                segment_indices.append(indexes_of_new_segments[2]);
                m_TriangleSubdomains.append(Subdomain(segment_indices, m_TriangleSubdomains[i].material()));
            }
        }
        //****************************************************************************************************************************
        //****************************************************************************************************************************
        return TriangleNet(m_TriangleElements, m_Points);
    }

    //================================================================================================================================
    //================================================================================================================================
    void FrontalTriangulation::prepareTriangleSubdomain(int subdomain)
    {
        //Сегменты a, b и c ограничивающие подобласть.
        BorderSegment &a = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(0)];
        BorderSegment &b = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(1)];
        BorderSegment &c = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(2)];

        //****************************************************************************************************************************
        //Переименование ребер
        //****************************************************************************************************************************
        if(a.numOfPoints() == b.numOfPoints());
        else if(a.numOfPoints() == c.numOfPoints())
        {
            QList<int> segment_indices;
            segment_indices.append(0);
            segment_indices.append(2);
            segment_indices.append(1);
            m_TriangleSubdomains[subdomain].reorderBorderSegments(segment_indices);
        }
        else if(b.numOfPoints()== c.numOfPoints())
        {
            QList<int> segment_indices;
            segment_indices.append(1);
            segment_indices.append(2);
            segment_indices.append(0);
            m_TriangleSubdomains[subdomain].reorderBorderSegments(segment_indices);
        }

        // Сегменты переорганизовали.
        BorderSegment &a_new = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(0)];
        BorderSegment &b_new = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(1)];
        BorderSegment &c_new = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(2)];

        //****************************************************************************************************************************
        //Переориентирование ребер
        //****************************************************************************************************************************
        if(a_new.firstPoint() == b_new.firstPoint());
        else if(a_new.firstPoint() == b_new.lastPoint())
            b_new.reverse();
        else if(b_new.firstPoint() == a_new.lastPoint())
            a_new.reverse();
        else
        {
            a_new.reverse();
            b_new.reverse();
        }

        if(c_new.firstPoint() != b_new.lastPoint())
            c_new.reverse();
    }

    //================================================================================================================================
    //================================================================================================================================
    void FrontalTriangulation::prepareQuadrangleSubdomain(int subdomain)
    {
        //Сегменты a, b, c и d ограничивающие подобласть.
        BorderSegment &a = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(0)];
        BorderSegment &b = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(1)];
        BorderSegment &c = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)];
        BorderSegment &d = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(3)];

        //****************************************************************************************************************************
        //Переименование ребер
        //****************************************************************************************************************************
        if(a.numOfPoints() == c.numOfPoints());
        else if(b.numOfPoints() == d.numOfPoints())
        {
            QList<int> segment_indices;
            segment_indices.append(1);
            segment_indices.append(2);
            segment_indices.append(3);
            segment_indices.append(0);
            m_QuadrangleSubdomains[subdomain].reorderBorderSegments(segment_indices);
        }

        // Сегменты переорганизовали.
        BorderSegment &a_new = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(0)];
        BorderSegment &b_new = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(1)];
        BorderSegment &c_new = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)];
        BorderSegment &d_new = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(3)];

        //****************************************************************************************************************************
        //Переориентирование ребер
        //****************************************************************************************************************************
        if(a_new.lastPoint() != b_new.firstPoint() && a_new.lastPoint() != b_new.lastPoint())
            a_new.reverse();
        if(a_new.lastPoint() == b_new.firstPoint())
            b_new.reverse();
        if(c_new.lastPoint() != b_new.firstPoint())
            c_new.reverse();
        if(d_new.firstPoint() != c_new.firstPoint())
            d_new.reverse();
    }

    //================================================================================================================================
    //================================================================================================================================
    void FrontalTriangulation::triangulateTriangleSubdomain(int subdomain)
    {
        int fe_points[3];
        QList<int> point_indices;
        QList<int> segment_indices;

        //****************************************************************************************************************************
        //Отдельно рассмотрим треугольник, у которого на двух ребрах нет внутренних узлов
        //****************************************************************************************************************************
        if(m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(0)].numOfPoints() == 2 &&
                m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(1)].numOfPoints() == 2)
        {
            for(int i = 0; i < m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(2)].numOfPoints() - 1; i++)
            {
                fe_points[0] = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(0)].point(0);
                fe_points[1] = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(2)].point(i);
                fe_points[2] = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(2)].point(i + 1);
                m_TriangleElements.append(TriangleElement(fe_points[0], fe_points[1], fe_points[2], m_TriangleSubdomains[subdomain].material()));
            }
        }
        //****************************************************************************************************************************
        //Дальше рассматривается общий случай. Разбиваем треугольник на маленький треугольничек и четырехугольник.
        //****************************************************************************************************************************
        else
        {
            fe_points[0] = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(0)].point(0);
            fe_points[1] = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(0)].point(1);
            fe_points[2] = m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(1)].point(1);
            m_TriangleElements.append(TriangleElement(fe_points[0], fe_points[1], fe_points[2], m_TriangleSubdomains[subdomain].material()));

            //-----

            point_indices.clear();
            for(int i = 1; i < m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(0)].numOfPoints(); i++)
                point_indices.append(m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(0)].point(i));

            m_BorderSegments.append(BorderSegment(point_indices));
            segment_indices.append(m_BorderSegments.size() - 1);

            //-----

            segment_indices.append(m_TriangleSubdomains[subdomain].borderSegment(2));

            //-----

            point_indices.clear();
            for(int i = 1; i < m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(1)].numOfPoints(); i++)
                point_indices.append(m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(1)].point(i));

            m_BorderSegments.append(BorderSegment(point_indices));
            segment_indices.append(m_BorderSegments.size() - 1);

            //-----

            point_indices.clear();
            point_indices.append(m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(0)].point(1));
            point_indices.append(m_BorderSegments[m_TriangleSubdomains[subdomain].borderSegment(1)].point(1));
            m_BorderSegments.append(BorderSegment(point_indices));
            segment_indices.append(m_BorderSegments.size() - 1);

            //-----
            m_QuadrangleSubdomains.append(Subdomain(segment_indices, m_TriangleSubdomains[subdomain].material()));
            prepareQuadrangleSubdomain(m_QuadrangleSubdomains.size() - 1);
            triangulateQuadrangleSubdomain(m_QuadrangleSubdomains.size() - 1);
        }
    }

    //================================================================================================================================
    //================================================================================================================================
    void FrontalTriangulation::triangulateQuadrangleSubdomain(int subdomain)
    {
        int fe_points[3];
        QList<int> point_indices;

        //****************************************************************************************************************************
        //Для добавления нового треугольника в разбиение к существующему базису(отрезок границы или сторона уже добавленного
        //треугольника) добавляется точка, которая соединяется с концами базисного отрезка, таким образом образуя новый треугольник.
        //Переменная base - это базисный отрезок, заданный номерами точек его концов
        //****************************************************************************************************************************
        int base[2];

        //****************************************************************************************************************************
        //Подобласть разбивается на ленты, таким образом, что все точки подобласти находятся на границах лент. Каждая лента разбивается
        //на конечные элементы отдельно. left_side и right_side - списки точек, принадлежащих левой и правой границам ленты и еще не
        //принадлежащин ни одному конечному элементу в этой ленте. next_left_side - список, используемый для того, чтобы избавиться от
        //лишних расчетов, поскольку правая сторона текущей ленты, будет левой стороной следующей ленты
        //****************************************************************************************************************************
        QList<int> left_side;
        QList<int> right_side;
        QList<int> next_left_side;

        for(int k = 0; k < m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(0)].numOfPoints() - 1; k++)
        {
            //************************************************************************************************************************
            //Формируем левую границу полосы. Если это первая полоса, то левая граница - это сторона d подобласти (без первой точки),
            //иначе, это изначальная правая сторона предыдущей ленты.
            //************************************************************************************************************************
            if(k == 0)
                for(int i = 1; i < m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(3)].numOfPoints(); i++)
                    left_side.append(m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(3)].point(i));
            else
                left_side = next_left_side;

            //************************************************************************************************************************
            //Формируем правую границу полосы. Если это первая полоса, то левая граница - это сторона d подобласти (без первой точки),
            //иначе, это отрезок, соединяющий соответствующие точки a и c.
            //************************************************************************************************************************
            if(k != m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].numOfPoints() - 2)
            {
                int m = (m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(3)].numOfPoints() -
                         m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(3)].numOfPoints()*(k + 1)/
                         m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].numOfPoints() +
                         m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(1)].numOfPoints()*(k + 1)/
                         m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].numOfPoints());

                double spacing_factor = (m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(3)].spacingFactor() -
                    m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(3)].spacingFactor()*(k + 1)/
                    m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].numOfPoints() +
                    m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(1)].spacingFactor()*(k + 1)/
                    m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].numOfPoints());

                if(qAbs(spacing_factor - 1) < DBL_EPSILON)
                {
                    for(int j = 0; j < m - 2; j++)
                    {
                        double r = m_Points[m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].point(k + 1)].x() +
                            (m_Points[m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(0)].point(k + 1)].x() -
                            m_Points[m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].point(k + 1)].x())*(j + 1)/(m - 1);
                        double z = m_Points[m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].point(k + 1)].y() +
                            (m_Points[m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(0)].point(k + 1)].y() -
                            m_Points[m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].point(k + 1)].y())*(j + 1)/(m - 1);

                        m_Points.append(Point(r,z));
                        right_side.append(m_Points.size() - 1);
                    }
                }
                else
                {
                    int begin = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].point(k + 1);
                    int end = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(0)].point(k + 1);
                    double w = abs(m_Points[begin].x() - m_Points[end].x())*(1 - spacing_factor)/(1 - pow(spacing_factor, m - 1));
                    double h = abs(m_Points[begin].y() - m_Points[end].y())*(1 - spacing_factor)/(1 - pow(spacing_factor, m - 1));

                    double x = m_Points[begin].x();
                    double y = m_Points[begin].y();

                    for(int j = 0; j < m - 2; ++j, w*=spacing_factor, h*=spacing_factor)
                    {
                        x += w;
                        y += h;
                        m_Points.append(Point(x,y));
                        right_side.append(m_Points.size() - 1);
                    }
                }

                right_side.append(m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(0)].point(k + 1));
                next_left_side = right_side;
            }
            else
                for(int i = 1; i < m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(1)].numOfPoints(); i++)
                    right_side.append(m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(1)].point(i));

            //************************************************************************************************************************
            //Формируем базис ленты(ее нижняя граница)
            //************************************************************************************************************************
            base[0] = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].point(k);
            base[1] = m_BorderSegments[m_QuadrangleSubdomains[subdomain].borderSegment(2)].point(k + 1);

            //************************************************************************************************************************
            //Точки есть в обеих полосах. Кондидаты в добавление - первые точки с каждой из полос. Добавляется та точка, для которой
            //отрезок соединяющий точку с концом базиса, принадлежащим другой стороне, меньше
            //************************************************************************************************************************
            while(right_side.size() != 0 && left_side.size() != 0)
            {
                if(distance(m_Points[base[0]], m_Points[right_side[0]]) < distance(m_Points[base[1]], m_Points[left_side[0]]))
                {
                    fe_points[0] = base[0];
                    fe_points[1] = base[1];
                    fe_points[2] = right_side[0];
                    m_TriangleElements.append(TriangleElement(fe_points[0], fe_points[1], fe_points[2], m_QuadrangleSubdomains[subdomain].material()));

                    base[1] = right_side[0];
                    right_side.removeAt(0);
                }
                else
                {
                    fe_points[0] = base[0];
                    fe_points[1] = base[1];
                    fe_points[2] = left_side[0];
                    m_TriangleElements.append(TriangleElement(fe_points[0], fe_points[1], fe_points[2], m_QuadrangleSubdomains[subdomain].material()));

                    base[0] = left_side[0];
                    left_side.removeAt(0);
                }
            }
            //************************************************************************************************************************
            //Точки только в левой границе
            //************************************************************************************************************************
            if(right_side.size() == 0)
            {
                while(left_side.size() != 0)
                {
                    fe_points[0] = base[0];
                    fe_points[1] = base[1];
                    fe_points[2] = left_side[0];
                    m_TriangleElements.append(TriangleElement(fe_points[0], fe_points[1], fe_points[2], m_QuadrangleSubdomains[subdomain].material()));

                    base[0] = left_side[0];
                    left_side.removeAt(0);
                }
            }
            //************************************************************************************************************************
            //Точки только в правой границе
            //************************************************************************************************************************
            else
            {
                while(right_side.size() != 0)
                {
                    fe_points[0] = base[0];
                    fe_points[1] = base[1];
                    fe_points[2] = right_side[0];
                    m_TriangleElements.append(TriangleElement(fe_points[0], fe_points[1], fe_points[2], m_QuadrangleSubdomains[subdomain].material()));

                    base[1] = right_side[0];
                    right_side.removeAt(0);
                }
            }
        }
    }

    //================================================================================================================================
    //================================================================================================================================
    int FrontalTriangulation::concatinateBorderSegments(int a,int b)
    {
        QList<int> point_indices;

        for(int i = 0; i < m_BorderSegments[a].numOfPoints(); i++)
            point_indices.append(m_BorderSegments[a].point(i));

        for(int i = 1; i < m_BorderSegments[b].numOfPoints(); i++)
            point_indices.append(m_BorderSegments[b].point(i));

        m_BorderSegments.append(BorderSegment(point_indices));
        return m_BorderSegments.size() - 1;
    }
}
